package work.lianbiao;

import work.ListNode;
import work.Node;

import java.util.HashMap;
import java.util.Map;

public class Problem138 {

    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    public Node copyRandomList123(Node head) {

        Node p = head;
        while (p != null) {
            Node node = new Node(p.val);
            node.next = p.next;
            p.next = node;
            p = node.next;
        }
        p = head;
        while (p != null) {
            if (p.random != null) {
                p.next.random = p.random.next;
            }
            p = p.next.next;
        }
        p = head;
        Node ans = new Node(0);
        Node ans1 = ans;
        while (p != null) {
            ans.next = p.next;
            ans = ans.next;
            p.next = ans.next;
            p = p.next;
        }
        return ans1.next;

    }


    //哈希法
    public Node copyRandomList1(Node head) {
        Map<Node, Node> map = new HashMap<>();
        Node node = head;
        while (node != null) {
            Node newNode = new Node(node.val);
            map.put(node, newNode);
            node = node.next;
        }
        node = head;
        while (node != null) {
            Node node1 = map.get(node);
            Node nodeNext = node.next;
            Node node2 = map.get(nodeNext);
            Node nodeRandom = node.random;
            Node node3 = map.get(nodeRandom);
            node1.next = node2;
            node1.random = node3;
            node = node.next;

        }
        Node ans = map.get(head);
        return ans;


    }

    public static void main(String[] args) {

    }


    public Node copyRandomList333(Node head) {
        Node temp = head;
        while (temp != null) {
            Node node = new Node(temp.val);
            node.next = temp.next;
            temp.next = node;
            temp = temp.next.next;
        }
        temp = head;
        while (temp != null) {
            if (temp.random != null) {
                temp.next.random = temp.random.next;
            } else {
                temp.next.random = null;
            }
            temp = temp.next.next;
        }
        Node ans = new Node(0);
        temp = head;
        Node cur = ans;
        while (temp != null) {
            cur.next = temp.next;
            cur = cur.next;
            temp.next = cur.next;
            temp = temp.next;
        }
        return ans;
    }


}
